package cn.kent.middle;

import java.util.Arrays;

/**
 * 209. 长度最小的子数组
 * 题目：
 * 给定一个含有 n 个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
 *
 * 注意： 连续数组问题，优先考虑 前缀和方法 和 滑动窗口方法
 */
public class MinSubArrayLen {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int i = minSubArrayLen3(11, nums);
        System.out.println(i);
    }

    /**
     * 滑动窗口
     * 时间复杂度： O(n)
     * 空间复杂度： O(1)
     */
    public static int minSubArrayLen3(int target, int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= target) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    /**
     * todo:
     * 前缀和+二分查找
     * 步骤：先计算前缀和，生成新数组，然后使用二分查找
     */
    public static int minSubArrayLen2(int target, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1];
        //  为了方便计算，令 size = n + 1
        //        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        //        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        //        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target2 = target + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target2);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    /**
     * 双层for循环 - 效率很低
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1) 没有使用额外空间
     */
    public static int minSubArrayLen(int target, int[] nums) {
        int res = 0;
        boolean bool = true;
        for (int i = 0; i < nums.length; i++) {
            int res2 = 0, sum = 0;
            for (int j = i; j < nums.length; j++) {
                res2++;
                sum += nums[j];
                if (sum >= target) {
                    res = bool ? res2 : Math.min(res, res2);
                    bool = false;
                    break;
                }
            }
        }
        return res;
    }

}
